package algorithm.sort.array;

/**
 * @program: algorithm-data-structure
 * @description: bubbling sort method.
 * @author: Keyu Li
 * @create: 2021-08-30 09:51
 **/

public class SortQuick implements SortingMethod {
    String name = "Quick";

    @Override
    public String getName() {
        return name;
    }

    @Override
    public void sort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int start, int end) {
        if (start >= end)
            return;
        int index = quickPartition(arr, start, end);
        quick(arr, start, index - 1);
        quick(arr, index + 1, end);
    }

    private int quickPartition(int[] arr, int start, int end) {
        int pivot = arr[end];
        int i = start, j = start;
        int temp;
        while (j < end) {
            if (arr[j] < pivot) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
            j++;
        }
        arr[end] = arr[i];
        arr[i] = pivot;
        return i;
    }
}
